package com.u17;

import java.time.chrono.MinguoChronology;

/**
 * @author u17
 * https://leetcode-cn.com/problems/climbing-stairs/
 */
public class Solution {

    /**
     * 递归，超时
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        return climbStairs(n - 1) + climbStairs(n - 2);

    }

    /**
     * 递归改进
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        int f1 = 0;
        int f2 = 0;
        int fn = 1;

        for (int i = 1; i <= n; i++) {
            f1 = f2;
            f2 = fn;
            fn = f1 + f2;
        }
        return fn;
    }



    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(10000));
    }

}
